;; https://projecteuler.net/problem=31

;; Coin sums
;; Problem 31

;; In the United Kingdom the currency is made up of pound
;; (£) and pence (p). There are eight coins in general
;; circulation:

;;     1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

;; It is possible to make £2 in the following way:

;;     1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

;; How many different ways can £2 be made using any number
;; of coins?


(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ)
 ;; (srfi srfi-69)  ; hash tables
 (srfi srfi-1)  ; reduce
 (contract)
 (prefix (lib math) math:)
 (lib print-utils))


(define coins
  '(200 100 50 20 10 5 2 1))


(define count-combinations
  (λ (coins to-pay)
    (cond
     [(= to-pay 0) 1]
     [(< to-pay 0) 0]
     [(null? coins) 0]
     [else
      (+
       ;; either use the highest coin and substract the
       ;; value from the amount to pay
       (count-combinations coins
                           (- to-pay (car coins)))
       ;; or don't use the highest coin and continue without
       ;; it
       (count-combinations (cdr coins)
                           to-pay))])))


(print "number of ways to pay:" (count-combinations coins 200))


;; Do different orders of coins count as separate solutions?
